home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 3080 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.3 KB
  1. Path: news.infi.net!usenet
  2. From: nngis@norfolk.infi.net (Greg DiGiorgio)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Sorting large files
  5. Date: 25 Jan 1996 20:44:24 GMT
  6. Organization: Customer of InfiNet
  7. Message-ID: <4e8q38$4va@nw002.infi.net>
  8. References: <4e8j9b$cuf@longwood.cs.ucf.edu>
  9. Reply-To: nngis@norfolk.infi.net
  10. NNTP-Posting-Host: h-standbyme.norfolk.infi.net
  11. Mime-Version: 1.0
  12. X-Newsreader: WinVN 0.99.3
  13.  
  14. In article <4e8j9b$cuf@longwood.cs.ucf.edu>, schnitzi@longwood.cs.ucf.edu 
  15. says...
  16. >
  17. >There was some discussion here a little while
  18. >back on how to sort the lines in a large file
  19. >without having to have a huge character array.
  20. >I suggested using ftell and fseek to hunt down
  21. >the particular lines you are comparing.  Only
  22. >just the other day did I notice (via a web
  23. >search engine) that someone posted a question
  24. >on how this could be done...  So here goes.
  25. >
  26. >... snipped ...
  27.  
  28. just throwing my 2 cents (perhaps 1.2 cents) in...
  29.  
  30. Sorting large files is a problem, especially if you try to do them in 
  31. memory. On mainframes, one buys an entire pkg devoted to sorting. In 
  32. UNIX, you use the "sort" cmd. RDBMS have to make use of optimized sorts 
  33. to provide fast reponse. Either way, I can not envision sorting large 
  34. files without temp work files to hold intermediate results. Let's assume 
  35. you have 1 million records of 100 bytes to sort - that's 100M of data.
  36.  
  37. Based on the number of records to sort, you could divide the input file, 
  38. say, into sets of 10,000 records. Sort each set into a work file. After 
  39. accumulating a number of sets, perform a merge-sort on those work files 
  40. into a single new work file. Del the other work files. Move on to the 
  41. next set of work files, merging them into another work file. Merge the 2 
  42. sorted work files and del the merged files. Do this until you have 
  43. completely sorted the data file.
  44.  
  45. The memory-based sort you use is your choice. Mainframe pkgs sample data 
  46. before sorting to choose the most optimized sorting method to use. I 
  47. mean, you have bubble sort and insertion sort on the low end and quick 
  48. sort & heap sort on the high end and probably 50 other sorting algorithms 
  49. I don't even know about.
  50.  
  51. Sorting data is such a technical issue, that mainframe RDBMS are even 
  52. resorting to sort progs implemented in hardware to speed this often-used 
  53. bottleneck.
  54.  
  55. Good luck on your course of action,
  56. Greg DiGiorgio
  57.  
  58.